<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        class BinarySearchTree {
            root = null
            static Node = class Node {
                constructor(key) {
                    this.key = key
                    this.left = null
                    this.right = null
                }
            }

            insert(key) {
                let newNode = new BinarySearchTree.Node(key)
                if (this.root === null) {
                    this.root = newNode
                    return
                }
                this.insertNode(this.root, newNode)
            }
            insertNode(node, newNode) {
                if (newNode.key < node.key) {
                    if (node.left === null) {
                        node.left = newNode
                    } else {
                        this.insertNode(node.left, newNode)
                    }
                } else if (newNode.key > node.key) {
                    if (node.right === null) {
                        node.right = newNode
                    } else {
                        this.insertNode(node.right, newNode)
                    }
                }
            }

            remove(key) {
                let current = this.root
                let parent = null
                let isLeftChild = true

                while (current.key !== key) {
                    parent = current
                    if (key < current.key) {
                        current = current.left
                        isLeftChild = true
                    } else if (key > current.key) {
                        current = current.right
                        isLeftChild = false
                    }
                    if (current === null) {
                        return false
                    }
                }
                // 没有子节点
                if (current.left === null && current.right === null) {
                    if (this.current === this.root) {
                        this.root = null
                    } else if (isLeftChild) {
                        parent.left = null
                    } else {
                        parent.right = null
                    }
                } else if (current.left === null) {
                    // 有一个子节点
                    if (current === this.root) {
                        this.root = current.right
                    } else if (isLeftChild) {
                        parent.left = current.right
                    } else {
                        parent.right = current.right
                    }
                } else if (current.right === null) {
                    if (current === this.root) {
                        this.root = current.left
                    } else if (isLeftChild) {
                        parent.left = current.left
                    } else {
                        parent.right = current.left
                    }
                } else {
                    // 有两个子节点
                    let successor = this.getSuccessor(current)

                    if (current === this.root) {
                        this.root = successor
                    } else if (isLeftChild) {
                        parent.left = successor
                    } else {
                        parent.right = successor
                    }

                    successor.left = current.left
                }
            }

            getSuccessor(delNode) {
                let successorParent = delNode
                let successor = delNode
                let current = delNode.right

                while (current !== null) {
                    successorParent = successor
                    successor = current
                    current = current.left
                }

                if (successor !== delNode) {
                    successorParent.left = successor.right
                    successor.right = delNode.right
                }

                return successor
            }
            
            midOrderTraversal(handler) {
                this.midOrderTraversalNode(this.root, handler)
            }

            midOrderTraversalNode(node, handler) {
                if (node !== null) {
                    //1.遍历左子树中的节点
                    this.midOrderTraversalNode(node.left, handler)

                    //2.处理节点
                    handler(node.key)

                    //3.遍历右子树中的节点
                    this.midOrderTraversalNode(node.right, handler)
                }
            }
        }


        let bst = new BinarySearchTree()
        bst.insert(11);
        bst.insert(7);
        bst.insert(15);
        bst.insert(5);
        bst.insert(3);
        bst.insert(9);
        bst.insert(8);
        bst.insert(10);
        bst.insert(13);
        bst.insert(12);
        bst.insert(14);
        bst.insert(20);
        bst.insert(18);
        bst.insert(25);
        bst.insert(6);
        bst.insert(19);

        //3.测试删除代码
        //删除没有子节点的节点
        bst.remove(3)
        bst.remove(8)
        bst.remove(10)

        //删除有一个子节点的节点
        bst.remove(5)
        bst.remove(19)

        //删除有两个子节点的节点
        bst.remove(9)
        bst.remove(7)
        bst.remove(15)
        console.log(bst)

        let resultString = ""
        bst.midOrderTraversal(function (key) {
            resultString += key + "->"
        })
        console.log(resultString)
    </script>
</body>

</html>